//
// Created by PC on 2017/12/26.
//

#ifndef DFSANDCOMPONENTS_SHORTESTPATH_H
#define DFSANDCOMPONENTS_SHORTESTPATH_H

#include <iostream>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

template <typename Graph>
class ShortestPath{
private:
    Graph &G;
    int *from;
    bool *visited;
    int *old;
    int s;
public:
    ShortestPath(Graph graph,int s):G(graph){
        assert(s>=0&&s<graph.V());
        this->s=s;
        visited = new bool[graph.V()];
        from = new int[graph.V()];
        old = new int[graph.V()];
        for (int i = 0; i <graph.V(); i++) {
            from[i]=-1;
            visited[i]= false;
            old[i]=-1;
        }
        queue<int> q;
        q.push(s);
        visited[s]= true;
        old[s]=0;
        while (!q.empty()) {
            int v= q.front();
            q.pop();

            typename Graph::adjIterator adj(G,v);
            for (int i = adj.begin();!adj.end();i=adj.next()) {
                if (!visited[i]) {
                    q.push(i);
                    visited[i]=true;
                    from[i]=v;
                    old[i]=old[v]+1;
                }
            }
        }

    }
    ~ShortestPath(){
        delete[] from;
        delete[] visited;
        delete[] old;
    }
    bool hasPath(int w){
        assert(w>=0&&w<G.V());
        return visited[w];
    }

    void path(int w,vector<int> &vec){
        assert(hasPath(w));
        stack<int> s;
        int p=w;
        while (p != -1) {
            s.push(p);
            p=from[p];
        }

        vec.clear();
        while(!s.empty()) {
            vec.push_back(s.top());
            s.pop();
        }

    }

    void showPath(int w){
        assert(hasPath(w));
        vector<int> vec;
        path(w,vec);
        for (int i = 0; i < vec.size(); i++) {
            cout<<vec[i];
            if (i==vec.size()-1)
                cout<<endl;
            else
                cout<<" -> ";
        }
    }

    int length(int w){
        assert(hasPath(w));
        return old[w];
    }


};
#endif //DFSANDCOMPONENTS_SHORTESTPATH_H
